import ListNode from "../common/list_node"
import { d1} from '../common/list_node'

//hash值
function hasCycle_hash(head: ListNode | null): boolean {
  if (head == null) return false
  let ret = false
  let set = new Set()
  while (head != null) {
    if(set.has(head)) {
      ret = true
      break
    }

    set.add(head)
    head = head.next
  }
  return ret
};
//走一样的路径，转圈.  刚开始疑惑，会不会相交，但是fast+2，正好把slow错过去，其实并不会。你推演slow落后三个身位，落后两个，落后一个，只要相交，肯定会相等
function hasCycle_hash_o1(head: ListNode | null): boolean {
  if (head == null) return false
  let slow:ListNode | null = head
  let fast:ListNode | null = head.next
  while(slow !=fast) {
    //打破循环,终止条件:fast到头
    if(fast == null || fast.next == null) {
      return false
    }
    slow = slow!.next
    fast = fast.next.next

  }

  return true
}
console.log(hasCycle_hash_o1(d1))